Merge k Sorted Lists
Leetcode #23 | Hard | Связный список | Куча
Идея
Через heap головных элементов, либо идея merge sort (а два листа мы умеем через два указателя)
Big-O
- Время
O(Nlog(K)) - Память
O(K)
N - количество нод во всех списках, K - количество связных списков (в куче всегда <=1 представитель от каждого списка)
Код
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode h : lists) if (h != null) heap.offer(h);
ListNode dummy = new ListNode(0), cur = dummy;
while (!heap.isEmpty()) {
ListNode min = heap.poll();
cur.next = min; cur = cur.next;
if (min.next != null) heap.offer(min.next);
}
return dummy.next;
}
}